import java.util.HashMap;
import java.util.Map;

class Solution115 {
    public int numDistinct(String s, String t) {
        char[] arrs = s.toCharArray() ;
        char[] arrt = t.toCharArray() ;

         int n = t.length() ;
         int m = s.length() ;
         int[][] dp = new int[n+1][m+1] ;
         for(int i=0 ; i <= m ; i ++) dp[0][i] = 1 ;
         for(int i=1 ; i <= n ; i ++){
             for(int j=1 ; j <= m ; j ++){
                 if(arrs[j-1] == arrt[i-1]){
                   dp[i][j] = dp[i-1][j-1] ;
                 }
                 dp[i][j] += dp[i][j-1] ;
             }
         }

        return dp[n][m] ;
    }
}